\section{Introduction}
In a dynamic network, nodes (processors/end hosts) and communication
links can appear and disappear over time.  Modern networking
technologies such as ad hoc wireless, sensor, mobile, overlay, and
peer-to-peer (P2P) networks are inherently dynamic,
bandwidth-constrained, and unreliable. This necessitates the
development of a solid theoretical foundation to design efficient,
robust, and scalable distributed algorithms and understand the power
and limitations of distributed computation on such networks. Such a
foundation is critical to realize the full potential of these
large-scale dynamic networks.

In this paper, we study a fundamental problem of information
spreading, called {\em $k$-gossip}, on dynamic networks.  This problem
was analyzed for static networks by Topkis~\cite{topkis:disseminate},
and was first studied on dynamic networks by Kuhn, Lynch, and
Oshman~\cite{kuhn+lo:dynamic}.  In $k$-gossip (also referred to as
{\em $k$-token dissemination}), there are $k$ distinct pieces of
information (tokens) that are initially present in some nodes and the
problem is to disseminate all the $k$ tokens to all the $n$ nodes in
the network, under the bandwidth constraint that one token can go
through an edge per round, under a synchronous model of communication.
This problem is a fundamental primitive for distributed computing;
indeed, solving $n$-gossip, where each node starts with exactly one
token, allows any function of the initial states of the nodes to be
computed, assuming the nodes know $n$~\cite{kuhn+lo:dynamic}.

\junk{Indeed, determining the time complexity of gossip is central to
  understanding the power of distributed computation in dynamic
  networks as well to understanding the fundamental algorithmic
  limitations and capabilities of various models of dynamic networks.}

The dynamic network models that we consider in this paper allow an
adversary to choose an arbitrary set of communication links among the
nodes for each round, with the only constraint being that the
resulting communication graph is connected in each round. Our
adversarial models are either the same as or closely related to those
adopted in recent
studies~\cite{avin+kl:dynamic,kuhn+lo:dynamic,odell+w:dynamic,santoro}.

\junk{ Our dynamic models subsume several well-studied models --- in
  particular, stochastic evolutionary models (e.g., see
  \cite{Markovian} and the references therein) --- in distributed
  computing and networking. }

The focus of this paper is on the power of {\em token-forwarding}\/
algorithms, which do not manipulate tokens in any way other than
storing, copying, and forwarding them.  Token-forwarding algorithms
are simple and easy to implement, typically incur low overhead, and
have been widely studied (e.g, see~\cite{leightonbook,pelegbook}).  In
any $n$-node static network, a simple token-forwarding algorithm that
pipelines token transmissions up a rooted spanning tree, and then
broadcasts them down the tree completes $k$-gossip in $O(n + k)$
rounds~\cite{topkis:disseminate, pelegbook}, which is tight since
$\Omega(n+k)$ rounds is a straightforward lower bound due to bandwidth
constraints.  The central question motivating our study is whether a
linear or near-linear bound is achievable for $k$-gossip on dynamic
networks.

\junk{Unlike prior models on dynamic networks, this
model does not assume that the network eventually stops changing and
requires that the algorithms work correctly and terminate even in
networks that change continually over time.}

\junk{and nodes do not know their neighbors for the current round before
they broadcast their messages. (Note that in this model, only edges
change and nodes are assumed to be fixed.)
(By just gossip, we mean $n$-gossip.)  }

\subsection{Our results}
Our first result, in Section~\ref{sec:lower}, is a lower bound for
$k$-gossip under a worst-case model due to~\cite{kuhn+lo:dynamic},
which we call the {\em strongly adaptive adversary}\/ model. We now
define the model and then state the theorem.

\begin{definition}[Strongly adaptive adv.]
\label{def:strong} 
In each round of the {\em strongly adaptive adversary}\/ model, each
node first chooses a token to broadcast to all its neighbors (without
knowing who they are), and then the adversary chooses an arbitrary
connected communication network for that round with the knowledge of
the tokens chosen by each node.
\end{definition}

%!
We note that the choice made by each node may depend arbitrarily on
the tokens held by that and other nodes.  Hence this model allows for
both distributed and centralized algorithms.

%!
\begin{theoremR}[\tAlgLower]
\label{thm:alg+lower} (a) Any randomized token-forwarding algorithm 
(centralized or distributed) for $k$-gossip needs $\Omega(nk/\log n +
n)$ rounds in the strongly adaptive adversary model starting from any
initial token distribution in which each of $k \le n$ tokens is held
by exactly one node. (b) In addition, the same bound holds with high
probability over an initial token distribution where each of the $n$
nodes receives each of $k \le n$ tokens independently with probability
$3/4$.
\end{theoremR}

%!
%We note our lower bound applies to even  centralized  and
%randomized algorithms and a large class of initial token
%distributions.
This result resolves an open problem raised in~\cite{kuhn+lo:dynamic},
improving their lower bound of $\Omega(n \log n)$ for $k = \omega(\log
n \log \log n)$, and matching their upper bound to within a
logarithmic factor.  Our lower bound also enables a better comparison
of token-forwarding with an alternative approach based on network
coding due to ~\cite{haeupler:gossip,haeupler+k:dynamic}. Assuming the
size of each message is bounded by the size of a token, network coding
completes $k$-gossip in $O(nk/\log n + n)$ rounds for $O(\log n)$-bit
tokens, and $O(n + k)$ rounds for $\Omega(n \log n)$ bit tokens.
Thus, for large token sizes, our result {\em establishes a factor
  $\Omega(\min\{n,k\}/\log n)$ gap between token-forwarding and
  network coding}, a significant new bound on the network coding
advantage for information dissemination.\footnote{The strongly
  adaptive adversary model allows each node to broadcast one token in
  each round, and thus our bounds hold regardless of the token size.}
Furthermore, for small token and message sizes (e.g., $O(\polylog(n))$
bits), we do not know of any algorithm (network coding, or otherwise)
that completes $k$-gossip against a strongly adaptive adversary in
$o(nk/\polylog(n))$ rounds.


\junk{In a key
result,~\cite{kuhn+lo:dynamic} showed that in their adversarial model,
$k$-gossip can be solved by token-forwarding in $O(nk)$ rounds, and
any deterministic online token-forwarding algorithm needs $\Omega(n
\log k)$ rounds. They also proved an $\Omega(nk)$ lower bound for a
restricted class of token-forwarding algorithms, called
knowledge-based algorithms.  Our main result is a new lower bound that
applies to {\em any}\/ token-forwarding algorithm for $k$-gossip.

We show that every token-forwarding algorithm for the $k$-gossip
problem takes $\Omega(n + nk/\log n)$ rounds against an adversary
that, at the start of each round, knows the randomness used by the
algorithm in the round.  This also implies that any deterministic
online token-forwarding algorithm takes $\Omega(n + nk/\log n)$
rounds.  Our result applies even to centralized token-forwarding
algorithms that have a global knowledge of the token distribution.}

\smallskip

Our lower bound for the strongly adaptive adversary model
motivates us to study models which restrict the power of
the adversary and/or strengthen the capabilities of the
algorithm. We would like to restrict the adversary power
as little as possible and yet design fast algorithms.

\begin{definition}[Weakly adaptive adv.]
\label{def:weak}
In each round of the {\em weakly adaptive adversary}\/ model, the
adversary is required to lay down the communication network first,
before the nodes can communicate. Hence nodes get to know their
neighbors and thus each node can send a possibly distinct token to
each of its neighbors.  Note that the adversary still has full control
of the topology in each round.
\end{definition}

%%%
We propose a simple protocol which we call the {\em symmetric difference}
(\symdiff) protocol.

\begin{definition}[\symdiff~protocol]
The protocol \symdiff~works as follows: in each round, independently
along every edge $(u,v)$, sample a token $t$ uniformly at random from
the symmetric difference (i.e., XOR) of the sets of tokens held by
node $u$ and node $v$ at the start of the round. Then the node that
holds $t$ sends it to the other node.
\end{definition}

Our second main result, in Section~\ref{sec:sym_diff_analysis}, shows
that in the weakly adaptive model, the \symdiff~protocol beats the
lower bound for mixed starting distribution of Theorem
\ref{thm:alg+lower}.

\begin{theoremR}[\trandsymdiff]
\label{thm:rand_sym_diff} Starting from any well-mixed distribution of tokens
where each of the $n$ nodes has each of the $k$ tokens independently
with a positive constant probability, the \symdiff~protocol completes
$k$-gossip in $O((n+k) \log n \log k)$ rounds with high
probability. The probability is both over the initial assignment of
tokens and the randomness of the protocol.
\end{theoremR}

\junk{We note that for this conjecture to be
true, randomization in the \symdiff~protocol is essential. Indeed, if the token
sent along an edge is selected deterministically from the symmetric difference,
as opposed to being selected at random, then we can exhibit a distribution on
$k$ tokens starting from which this protocol takes $\Omega(nk)$ rounds (see
Theorem \ref{thm:det_sym_diff}).}

%In addition to round complexity, an important parameter
%of protocols for the gossip problem is the amount of
%communication exchanged along each edge during a round.
%!It is non-trivial to implement the \symdiff~protocol in a
%!communication-efficient manner.
A communication-efficient implementation of \symdiff~hinges on the
communication complexity of sampling a uniform element from the
symmetric difference of two sets. As another technical contribution,
we give an explicit, communication-efficient protocol for this task in
Section~\ref{sec:sym_diff_sampling}.
%two players, holding subsets $A,B \subseteq [n]$,
%to sample uniformly at random from the symmetric
%difference set $A \oplus B$:

\begin{theoremR}[\tccSample]
\label{thm:sym_diff_sampling} Let Alice and Bob have two subsets $A \subseteq
[k]$ and $B \subseteq [k]$ respectively. There is an explicit, private-coin
protocol to sample a random element from the symmetric difference of the two
sets, $A \oplus B := (A \setminus B) \cup (B \setminus A)$, such that the
sampled distribution is statistically $\epsilon$-close to the uniform
distribution on $A \oplus B$ and the protocol uses $O(\log^{3/2} (k/\epsilon))$
bits of communication.
%The protocol outputs $\perp$ if the symmetric difference is empty.
\end{theoremR}

%As discussed in Section~\ref{sec:weakly_adaptive},
A recent improvement on pseudorandom generators for combinatorial
rectangles~\cite{GMRTV12} implies an improvement in the communication in
Theorem \ref{thm:sym_diff_sampling} to $\tilde O(\lg k/\eps)$.
We also note that for \symdiff~to be
communication-efficient it is important that we work with symmetric
difference as opposed to set difference, which might have looked a
natural choice.  This is because Theorem~\ref{thm:sym_diff_sampling}
becomes false if we replace symmetric difference $A \oplus B$ with set
difference $A \setminus B$. For the latter, communication $\Omega(k)$
is required, due to the lower bounds for
disjointness~\cite{KalyanasundaramS92,Razborov92}.


%The above theorem uses Lu's pseudorandom generator for combinatorial rectangles
%\cite{Lu02}
%(cf.~\cite{Nis92,NiZ96,INW94,EvenGLNV98,ArmoniSWZ96,Lu02,Viola-rbd}). Any
%improvement on such generators would reflect into a corresponding improvement in
%our sampling protocol, reaching communication $\tilde O(\log n/\epsilon)$.


%%%

\junk{ We propose \symdiff, a simple randomized distributed algorithm where in
each round, along every edge $(u,v)$, a token selected uniformly at random from
the symmetric difference of the sets of tokens held by node $u$ and node $v$ is
exchanged.
\begin{theoremR}[\tSymDiffProtocol]
\label{thm:rand_sym_diff}
In the weakly adaptive adversary model, from an initial distribution
of tokens where each node has each token with probability
$\frac{3}{4}$ independently, randomized \symdiff\ completes $k$-gossip
in $O(n \log n \log k)$ rounds with high probability.
\end{theoremR}

A critical component in \symdiff\ is the uniform selection of a token
from the symmetric difference of the sets of tokens held by two
neighboring nodes.  We show that that the uniform selection problem
can be solved with $O(\log^{1.5} n)$ bits of communication, making the
overall algorithm communication-efficient.

\begin{theoremR}[\tSymDiffSampling]
\label{thm:sym_diff_sampling}
Let Alice and Bob have two subsets $A \subseteq [n]$ and $B \subseteq
[n]$ respectively. There is an explicit protocol to sample a random
element from the symmetric difference of the two sets, $(A \setminus
B) \cup (B \setminus A)$, such that the sampled distribution is
statistically $\epsilon$-close to the uniform distribution on the
symmetric difference and the protocol uses $O(\log^{\frac{3}{2}} n +
\log^{\frac{3}{2}} (\frac{1}{\epsilon}))$ bits of communication. The
protocol outputs $\perp$ if the symmetric difference is empty.
\end{theoremR}
}

\junk{ We prove that starting from any {\em well-mixed}\/ distribution of
tokens, this algorithm solves $k$-gossip against a weakly adaptive adversary in
$O((n+k)\log n)$ rounds with high probability. We then show how the above
uniform selection problem can be solved with $O(\log^{1.5} n)$ bits of
communication, making the overall algorithm communication-efficient. }

%!
%Recall that we conjectured that \symdiff\ solves $k$-gossip for {\em every}\/
%initial token distribution against a weakly adaptive adversary in
%$\tilde{O}((n+k))$ rounds.

\smallskip
Although we have only been able to establish the efficiency of the
\symdiff~protocol starting from well-mixed distributions as in Theorem
\ref{thm:rand_sym_diff}, we conjecture that in fact \symdiff~is
efficient starting from any token distribution.  A priori, however, it
is unclear if there is {\em any}\/ token-forwarding algorithm that
solves $k$-gossip in $\tilde{O}(n+k)$ rounds even in an offline
setting, in which the network can change arbitrarily each round, but
the entire evolution is known to the algorithm in advance.  Our next
result, in Section~\ref{sec:multiport}, resolves this problem.

\begin{definition}[Offline algorithm]
\label{def:offline}
An {\em offline algorithm}\/ for $k$-gossip takes as input an initial
token distribution and a sequence of $nk$ graphs $G_1$, \ldots,
$G_{nk}$, where $G_t$ represents the communication network in round
$t$.  The output of the algorithm is a schedule that specifies, for
each $t$, each edge $e$ of $G_t$, a token (if any) sent along $e$ in
each direction.  The {\em length}\/ of the schedule is the largest $t$
for which a token is sent on any edge in round $t$.
\end{definition}

\begin{theoremR}[\tOfflineMultiport]
\label{thm:offline_multiport}
There is a polynomial-time randomized offline algorithm that returns,
for every $k$-gossip instance, a schedule of length $O((n+k)\log^2 n)$
with high probability.
\end{theoremR}

\junk{
\begin{itemize}
\item
We present a polynomial-time algorithm that given any $k$-gossip
instance on an $n$-node dynamic network, computes an offline schedule
for solving the instance in $O((n+k)\log^2 n)$ rounds, with high
probability.
\end{itemize}
}

Like \symdiff, the schedule returned by the above offline algorithm
allows each node to send a possibly distinct token to each of its
neighbors in each round. However, in some applications, e.g., wireless
networks, the preferred mode of communication is broadcast.  Hence, we
also consider offline broadcast schedules where each node can only
broadcast a single token to all of its neighbors in each round and
show the following result in Section~\ref{sec:upper}.

\begin{theoremR}[\tOfflineBroadcast]
\label{thm:offline_broadcast}
There is a polynomial-time randomized offline algorithm that returns,
for every $k$-gossip instance, a broadcast schedule of length $O(n
\min\{k, \sqrt{k \log n}\})$, with high probability.
\end{theoremR}

\junk{
\item
We present a polynomial-time algorithm that given any $k$-gossip
instance on an $n$-node dynamic network, computes an offline broadcast
schedule for solving the instance in $O(n \min\{k, \sqrt{k \log n}\})$
rounds, with high probability.
\end{itemize}
}
\junk{
We present a polynomial-time centralized algorithm that solves the
$k$-gossip problem in the offline setting of an $n$-node dynamic
network in $O(\min\{nk, n \sqrt{k \log n}\})$ rounds with high
probability.  We also present a polynomial-time centralized
token-forwarding algorithm that solves the $k$-gossip problem in the
offline setting in $O(n^\eps)$ times the optimal number of rounds, for
any $\eps > 0$, assuming the algorithm is allowed to transmit $O(\log
n)$ tokens per round.

Our upper bounds show that in the offline setting, token-forwarding
algorithms can achieve a time bound that is within $O(\sqrt{k\log n})$
of the information-theoretic lower bound of $\Omega(n + k)$, and that
we can approximate the best token-forwarding algorithm to within a
$O(n^\eps)$ factor, with logarithmic extra bandwidth per edge.
}

%\input{techniques}

\subsection{Related work}
Information spreading (or dissemination) in networks is a fundamental
problem in distributed computing and has a rich literature. The
problem is generally well-understood on static networks, both for
interconnection networks~\cite{leighton:book} as well as general
networks~\cite{lynch:distributed,pelegbook,attiya+w:distributed}.  In
particular, the $k$-gossip problem can be solved in $O(n + k)$ rounds
on any $n$-node static network~\cite{topkis:disseminate}.  There also
have been several papers on broadcasting, multicasting, and related
problems in static heterogeneous and wireless networks (e.g.,
see~\cite{alon+blp:radio,bar-yehuda+gi:radio,bar-noy+gns:multicast,clementi+mps:radio}).

Dynamic networks have been studied extensively over the past three
decades.  Early studies focused on dynamics that arise when edges or
nodes fail.  A number of fault models, varying according to extent and
nature (e.g., probabilistic vs.\ worst-case) of faults allowed, and
the resulting dynamic networks have been analyzed (e.g.,
see~\cite{attiya+w:distributed,lynch:distributed}).  There have been
several studies that constrain the rate at which changes occur, or
assume that the network eventually stabilizes (e.g.,
see~\cite{afek+ag:dynamic,dolev:stabilize,gafni+b:link-reversal}).

There also has been considerable work on general dynamic networks.
Early studies in this area
include~\cite{afek+gr:slide,awerbuch+pps:dynamic}, which introduce
building blocks for communication protocols on dynamic networks.
Another notable work is the local balancing approach
of~\cite{awerbuch+l:flow} for solving routing and multicommodity flow
problems on dynamic networks, which has also been applied to
multicast, anycast, and broadcast problems on mobile ad hoc
networks~\cite{awerbuch+bbs:route,awerbuch+bs:anycast,jia+rs:adhoc}.
To address highly unpredictable network dynamics, stronger adversarial
models have been studied
by~\cite{avin+kl:dynamic,odell+w:dynamic,kuhn+lo:dynamic} and others;
see the recent survey of \cite{santoro} and the references therein.
Unlike prior models on dynamic networks, these models and ours do not
assume that the network eventually stops changing; the algorithms are
required to work correctly and terminate even in networks that change
continually over time.  The recent work of \cite{clementi-podc12},
studies the flooding time of {\em Markovian} evolving dynamic graphs,
a special class of evolving graphs.
%We
%adopt the model of~\cite{kuhn+lo:dynamic} in which the set of remains
%fixed but the communication graph can change completely from round to
%round, with the only constraint being that it stays connected in each
%round.
 \junk{The model of~\cite{kuhn+lo:dynamic} allows for a much stronger
   adversary than the ones considered in past
   work~\cite{awerbuch+l:flow,awerbuch+bbs:route,awerbuch+bs:anycast}.
   There also have been other prior models for dynamic networks
   similar in spirit to the model of , In addition to the $k$-gossip
   problem,~\cite{kuhn+lo:dynamic} considers the related problem of
   counting, and generalizes its results to the $T$-interval
   connectivity model, which includes the constraint that any interval
   of $T$ rounds has a stable connected spanning subgraph. } The
 survey of~\cite{kuhn-survey} summarizes recent work on dynamic
 networks.  We also note that our model and the ones we have discussed
 thus far only allow edge changes from round to round; the recent work
 of \cite{p2p-soda} studies a dynamic network model where both nodes
 and edges can change in each round.  \junk{They show that stable
   almost-everywhere agreement can be efficiently solved in such
   networks even in adversarial dynamic settings. }

\junk{ .  Local balancing algorithms, which continually balance the
  packet queues across each edge of the network and drain packets at
  their destination,

It has been shown that assuming the queues at the nodes can hold
enough packets, the local balancing approach can achieve throughput
that is arbitrarily close to the optimal achievable by any offline
algorithm.

Modeling general dynamic networks has gained renewed attention with
the recent advent of heterogeneous networks composed out of ad hoc,
and mobile devices.  

The work of~\cite{avin+kl:dynamic} studied the {\em cover time} of random walks
in a dynamic network controlled by an adversary that is oblivious to
the random choices made by the nodes (this is a weaker model than the
adaptive models considered in this paper). 
}

 \junk{As in the Kuhn
  et al. model, the algorithms in \cite{p2p-soda} will work and
  terminate correctly even when the network keeps continually
  changing.  We note that there has been considerable prior work in
  dynamic P2P networks (see \cite{p2p-soda, p2p-focs} and the
  references therein) but these don't assume that the network keeps
  continually changing over time.}

Recent work of~\cite{haeupler:gossip,haeupler+k:dynamic} presents
information spreading algorithms based on network
coding~\cite{ahlswede+cly:coding}.  As mentioned earlier, one of their
important results is that the $k$-gossip problem on the adversarial
model of~\cite{kuhn+lo:dynamic} can be solved using network coding in
$O(n+k)$ rounds assuming the token sizes are sufficiently large
($\Omega(n\log n)$ bits). For further references to using network
coding for gossip and related problems, we refer to
~\cite{haeupler:gossip,haeupler+k:dynamic,avin1,avin2,deb+mc:coding,shah}
and the references therein.

As we show in Section~\ref{sec:upper}, the problem of finding an
optimal broadcast schedule in the offline setting reduces to the
Steiner tree packing problem for directed
graphs~\cite{cheriyan+s:steiner}.  This problem is closely related to
the directed Steiner tree problem (a major open problem in
approximation
algorithms)~\cite{charikar+ccdgg:steiner,zosin+k:steiner} and the gap
between network coding and flow-based solutions for multicast in
arbitrary directed networks~\cite{agarwal+c:coding,sanders+et:flow}.

Finally, we note that a number of recent studies solve $k$-gossip and
related problems using {\em gossip-based}\/ processes, in which each
node exchanges information with a small number of randomly chosen
neighbors in each round,
%These processes are attractive owing to
%their simplicity of implementation, scalability, and their use in
%aggregate computations,
e.g., see ~\cite{berenbrink+ceg:gossip,demers,kempe1,chen-spaa,karp,shah,boyd}
and the references therein.  All these studies assume a static
communication network, and do not apply directly to the models
considered in this paper.
%A related recent work
%is~\cite{avin+kl:dynamic} which analyzes the cover time of random
%walks on dynamic networks.
